/*6.50 假设以三元组（F，C，L/R）的形式输入一棵二叉树的诸边（其中F表示双亲结点的标识，C表示孩子结点标识，L/R表示C为F的左孩子或右孩子），且在输入的三元组序列中，C是按层次顺序出现的。设结点的标识是字符类型。F=‘^’时C为根结点标识，若C也为‘^’，则表示输入结束。例如，6.15题所示的二叉树的三元组序列输入格式为：
                    ^AL
                    ABL
                    ACR
                    BDL
                    CEL
                    CFR
                    DGR
                    FHL
                    ^^L
                    图见6.50.png
// 试编写算法，由输入的三元组序列建立二叉树的二叉链表。*/
#include <stdio.h>
#include <stdlib.h>
typedef struct tree
{
    char data;
    struct tree *left, *right;
};
void fun_6_50(tree *&root)
{
    tree *que[100];
    int rear, front;
    rear = front = 0;
    char p, c, t; //p :parent c :self t:left or right
    p = getchar();
    c = getchar();
    t = getchar();
    while (p != '^' || c != '^')
    {
        if (p == '^')
        {
            root = (tree *)malloc(sizeof(tree));
            root->data = c;
            root->left = root->right = NULL;
            que[rear++] = root;
            char _n = getchar(); //read '\n' BUG
            p = getchar();
            c = getchar();
            t = getchar();
        }
        else
        {
            if (root)
            {
                tree *temp = que[front];
                while (front < rear && p != temp->data)
                {
                    temp = que[++front];
                }
                tree *n = (tree *)malloc(sizeof(tree));
                n->data = c;
                n->right = n->left = NULL;
                switch (t)
                {
                case 'l':
                case 'L':
                    temp->left = n;
                    break;
                case 'r':
                case 'R':
                    temp->right = n;
                    break;
                default:
                    break;
                }
                char _n = getchar();
                p = getchar();
                c = getchar();
                t = getchar();
            }
        }
    }
}

int main()
{
    /*******************code*******************/
    tree *root = NULL;
    fun_6_50(root);
    /******************************************/
    printf("\n\n****************************\n");
    printf("Press Enter key to continue\n");
    getchar();
    return 0;
    /******************************************/
}
